% validate_solution.m
% 验证最终的解决方案是否有效。
% (版本 18: 修复了多次Spill无法验证的核心设计缺陷)

function is_valid = validate_solution(solution, graph, code_map, l1_cap, ub_cap, l0a_cap, l0b_cap, l0c_cap)
    
    is_valid = false;

    buf_info_map = containers.Map('KeyType', 'int32', 'ValueType', 'any');
    for i = 1:length(graph.nodes)
        node = graph.nodes(i);
        if isempty(node.id), continue; end
        
        if node.op_code == code_map.ALLOC && ~isempty(node.buf_id) && ~isempty(node.size)
            buf_info_map(node.buf_id) = {node.size, node.type_code};
        end
    end

    node_positions = containers.Map('KeyType', 'int32', 'ValueType', 'double');
    for i = 1:length(solution.final_schedule)
        node_positions(solution.final_schedule(i)) = i;
    end
    
    for u = 1:graph.num_nodes
        if ~isKey(node_positions, u), continue; end
        u_node = graph.nodes(u);
        if strcmp(u_node.op, 'SPILL_IN') || strcmp(u_node.op, 'SPILL_OUT'), continue; end
        
        successors = graph.adj_list{u};
        for i = 1:length(successors)
            v = successors(i);
            if ~isKey(node_positions, v), continue; end
            v_node = graph.nodes(v);
            if strcmp(v_node.op, 'SPILL_IN') || strcmp(v_node.op, 'SPILL_OUT'), continue; end

            if node_positions(u) > node_positions(v)
                fprintf(2, '验证失败: 拓扑序错误! 节点 %d (位置 %d) 出现在其后继节点 %d (位置 %d) 之后。\n', u, node_positions(u), v, node_positions(v));
                return;
            end
        end
    end
    fprintf('拓扑序检查通过。\n');

    cache_managers = containers.Map('KeyType', 'int32', 'ValueType', 'any');
    cache_managers(code_map.L1) = cm_create(l1_cap);
    cache_managers(code_map.UB) = cm_create(ub_cap);
    cache_managers(code_map.L0A) = cm_create(l0a_cap);
    cache_managers(code_map.L0B) = cm_create(l0b_cap);
    cache_managers(code_map.L0C) = cm_create(l0c_cap);

    l0_active = containers.Map({code_map.L0A, code_map.L0B, code_map.L0C}, {0, 0, 0});
    active_buffers = containers.Map('KeyType', 'int32', 'ValueType', 'any');
    
    for step = 1:length(solution.final_schedule)
        node_id = solution.final_schedule(step);
        node = graph.nodes(node_id);

        if strcmp(node.op, 'SPILL_IN') || (isfield(node, 'op_code') && node.op_code == code_map.ALLOC)
            buf_id = node.buf_id;
            if isempty(buf_id), continue; end

            if node.op_code == code_map.ALLOC
                if isempty(node.size)
                    fprintf(2, '验证失败: 在步骤 %d, 节点 %d (BufId: %d) 是一个 ALLOC 操作，但缺少 size 属性。\n', step, node_id, buf_id);
                    return;
                end
                if ~isKey(solution.memory_offsets, buf_id)
                    fprintf(2, '验证失败: 解决方案未包含 buf_id %d 的偏移量。\n', buf_id);
                    return;
                end
                offset = solution.memory_offsets(buf_id);
                size = node.size;
                type_code = node.type_code;
            else % SPILL_IN
                % *** 已修正: 使用 SPILL_IN 节点的 node_id 作为键 ***
                if ~isKey(solution.spill_map, node_id)
                    fprintf(2, '验证失败: 解决方案未包含 SPILL_IN 节点 %d 的偏移量。\n', node_id);
                    return;
                end
                offset = solution.spill_map(node_id);
                if ~isKey(buf_info_map, buf_id)
                    fprintf(2, '验证失败: 无法找到 buf_id %d 的原始信息。\n', buf_id);
                    return;
                end
                info = buf_info_map(buf_id);
                size = info{1};
                type_code = info{2};
            end

            manager = cache_managers(type_code);
            [manager, success] = cm_allocate_at(manager, size, buf_id, offset);
            
            if ~success
                fprintf(2, '验证失败: 在步骤 %d, 节点 %d (BufId: %d) 分配地址 %d (大小 %d) 时发生冲突。\n', step, node_id, buf_id, offset, size);
                return;
            end
            cache_managers(type_code) = manager;
            active_buffers(buf_id) = type_code;

            if l0_active.isKey(type_code)
                l0_active(type_code) = l0_active(type_code) + 1;
                if l0_active(type_code) > 1
                    fprintf(2, '验证失败: L0约束违反，在 type_code %d 中有多个激活的buffer。\n', type_code);
                    return;
                end
            end

        elseif (isfield(node, 'op_code') && node.op_code == code_map.FREE) || strcmp(node.op, 'SPILL_OUT')
            if isempty(node.buf_id), continue; end
            buf_id = node.buf_id;
            if isKey(active_buffers, buf_id)
                type_code = active_buffers(buf_id);
                
                manager = cache_managers(type_code);
                manager = cm_free(manager, buf_id);
                cache_managers(type_code) = manager;
                
                remove(active_buffers, buf_id);

                if l0_active.isKey(type_code)
                    l0_active(type_code) = l0_active(type_code) - 1;
                end
            end
        end
    end
    fprintf('内存分配模拟检查通过。\n');
    
    is_valid = true;
    fprintf('验证器执行完毕，未发现明显错误。\n');
end